We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distribution $D$, and we are interested in designing a (truthful) mechanism that has good performance for all true distributions that are close to $D$ in Total Variation (TV) distance. We show that DSIC and BIC mechanisms in this setting are strongly robust with respect to TV distance, for any bounded objective function $\mathcal{O}$, extending a recent result of Brustle et al. ([BCD20], EC 2020). At the heart of our result is a fundamental duality property of total variation distance. As direct applications of our result, we (i) demonstrate how to find approximately revenue-optimal and approximately BIC mechanisms for weakly dependent prior distributions; (ii) show how to find correlation-robust mechanisms when only ``noisy'' versions of marginals are accessible, extending recent results of Bei et.

Post-rebuttal: After reading the authors' response and further consideration, I am downgrading my score to 7 from 9. While I am still very excited about the new perspective this work brings, I now realize that there is still a lot of work remaining in order to tie the theoretical results to real-world phenomena. Regardless of whether the paper gets accepted, I'd ask the authors to make the gap clearer and to lay out more clearly an agenda for future work that address the various issues discussed in the rebuttal, e.g.: approximation, empirical notions of filling, etc. ORIGINALITY The paper considers the functional space of polynomial networks as an algebraic object. They use tools from algebraic geometry to analyze the dimension of the Zariski closure of this space. The paper is highly original in relating recent results from algebra to basic issues about neural networks. QUALITY & CLARITY This work tackles head-on the problem of analyzing the functional space of polynomial varieties.

We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distribution D, and we are interested in designing a (truthful) mechanism that has good performance for all "true distributions" that are close to D in Total Variation (TV) distance. We show that DSIC and BIC mechanisms in this setting are strongly robust with respect to TV distance, for any bounded objective function \mathcal{O}, extending a recent result of Brustle et al. ([BCD20], EC 2020). At the heart of our result is a fundamental duality property of total variation distance. As direct applications of our result, we (i) demonstrate how to find approximately revenue-optimal and approximately BIC mechanisms for weakly dependent prior distributions; (ii) show how to find correlation-robust mechanisms when only noisy'' versions of marginals are accessible, extending recent results of Bei et.

We provide a general framework for computing lower-bounds on the sample complexity of recovering the underlying graphs of Ising models, given i.i.d. While there have been recent results for specific graph classes, these involve fairly extensive technical arguments that are specialized to each specific graph class. In contrast, we isolate two key graph-structural ingredients that can then be used to specify sample complexity lower-bounds. Presence of these structural properties makes the graph class hard to learn. We derive corollaries of our main result that not only recover existing recent results, but also provide lower bounds for novel graph classes not considered previously. We also extend our framework to the random graph setting and derive corollaries for Erdos-Renyi graphs in a certain dense setting.